public class code01 {
    // 力扣 150 排序链表
    public ListNode sortList(ListNode head) {
        // 解法一：最合理的解法，使用将链表分割归并的思想对数组进行重组
        // 首先针对 head 的特殊情况进行返回判断
        if(head == null || head.next == null) {
            return head;
        }
        // 定义出快慢指针
        // 快指针是慢指针的两倍速度，最终慢指针能够的到中间位置的元素
        ListNode fast = head.next;
        ListNode slow = head;

        // 进行 while 循环，找到中心点
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 通过 slow 找到后半部分的开头节点
        ListNode center = slow.next;
        // 将数组分为两半，断开 slow.next
        slow.next = null;

// 上半部分实现的是划分操作，递归过来的部分都会在上面进行细分
// ——————————————————————————————————————————————
// 下半部分实现的是递归操作，并且处理递归结束之后元素的重新组合

        // 进行递归操作
        // 针对左半部分进行递归划分
        ListNode left = sortList(head);
        ListNode right = sortList(center);
        // 定义一个全新的头结点，用来拼接新的链表
        ListNode newHead = new ListNode(0);
        ListNode flag = newHead;

        // 处理之后的拼接问题
        while(left != null && right != null) {
            if(left.val < right.val) {
                flag.next = left;
                left = left.next;
            } else {
                flag.next = right;
                right = right.next;
            }
            // 将新链表的标记位向后移动
            flag = flag.next;
        }

        // 对称的要素拼接完成后，还需要对剩下的元素进行处理
        if(left == null) {
            flag.next = right;
        } else {
            flag.next = left;
        }

        // 最终返回链表的第二个节点
        return newHead.next;
    }
}
